Benes networks are non blocking networks. That is, given any permutation between the N inputs and N outputs of the network, the switches of the network can be set to connect the inputs to the specified outputs. This property of the Benes networks makes them particularly attractive for interprocessor communication in SIMD machines. Because of the non-blocking nature of Benes networks, the communication latencies are always constant, and therefore communication over the network can be synchronized with the calculations being performed by the processors on an instruction by instruction basis. This results in very low hardware and software overhead in communication, and communication can be effectively overlapped with calculations.
Several algorithms are known for finding a switch setting for a Benes network so that a given permutation will be realized on the network. All these algorithms require several hundred thousand instructions to find the switch setting for one communication pattern in a 576.times.576 network. Therefore, to efficiently execute a program on a SIMD machine with a Benes network, the communication patterns used in the program must be identified either at compile time, or at least several hundred thousand cycles prior to their actual use during the execution of the program. If a large number of communication patterns get defined dynamically during the execution of a program, each of the communication patterns should be used several hundred thousand times to amortize the delay in calculating the switch setting for it.
While most applications, when programmed on SIMD machines, require only compile time identifiable communication patterns, some applications (such as those which employ adaptive grid refinement) fail to meet this criterion. In these applications the communication patterns are defined during the execution of a program shortly before their use, and they are used relatively few times. To execute such programs efficiently on a SIMD machine with a Benes network, it is important to have a method for finding the switch settings in a much shorter time.
Thus, Benes networks are very effective in providing inter-processor communication in SIMD parallel machines, provided the communication patterns are compile-time determinable. These networks are ill suited when communication patterns are dynamically varying, however, because of the long set up time requirements. The present invention is a method for efficiently handling dynamically-varying communication patterns.